//【案例开放023】上机编程题之性能学习交流
//日期：2021-02-26 14:39浏览：19777回复：32026-09-18 失效
//在2020年8月17日后公司的生存环境发生了很大的变化，需要在芯片能力受限的情况下，通过软件性能提升来实现我们的产品综合竞争力的不落后和领先，
//提升软件性能自然成为了提升产品综合竞争力的主要手段。--摘自《对2021年软件工程能力提升变革的总体策略与要求》。
//按照性能问题解决方法的复杂程度，从低到高可分为三个层次：
// l  需要关注性能，避免低效的解法
// l  使用语言标准库和常用数据结构即可达到性能要求
// l  利用高效算法提升性能
// 1.   需要关注性能，避免低效的解法
//认证题目：2020-04-03 高铁选座­­（参数范围大，但是计算量不大）
// a)   题目描述
//在某趟高铁列车上，每个车厢内共有 rows 行座位，每行/列座位的序号和分布如示例 1
//的图示。 注："ABC DF"，"C" 与 "D" 间的空格表示车厢内的过道，列名仅由
//"A"、"B"、"C"、"D"、"F"表示，并且都是大写。 列表 seats
//中保存了此车厢已被购买的座位。若列表为空，表示该车厢内的座位还未被购买，且每个座位只能被购买一次。
//根据 seats 显示的售卖情况，请问可以订到多少对（2 张）同一行相邻的座位（"C" 和
//"D" 跨过道不相邻）。 示例 1： 输入：rows = 4, seats = ["3A","4F","3B"] 输出：6
//解释：还剩 6 个双人座供 6 对旅客选择，下图为情况之一
// 注：此图仅展示一种选择情况，若第一排过道左侧选择 1B 和
// 1C（二四排同理）也是满足选择条件的。限制：
//•   1 <= rows <= 10^9（非列车现实场景）
//•   0 <= seats.length <= 10^5，座位编号类似 "999999A" 表示 999999 行 A
//列。保证用例都是合法的数字和字母。 b)  解法不当，导致超时
//座位行数为10^9，10的9次方是10亿，如果全部遍历会超时；代码如下（以C++为例）：
//合理的解法举例
// seats.length是10的5次方（10万的数量级）；由于每一行的座位数是固定的，所以只需要计算总的座位数再减去已经售卖的座位数就可以了。Java代码：
class Solution {
 public
  int numSeats(int rows, String[] seats) {
    HashMap<String, String> seatRow = new HashMap<>();
    for (String row : seats) {
      String key = row.substring(0, row.length() - 1);
      seatRow.put(
          key, seatRow.getOrDefault(key, "") + row.substring(row.length() - 1));
    }
    int sum = 2 * rows;
    for (String seat : seatRow.values()) {
      if (seat.contains("B") || (seat.contains("A") && seat.contains("C"))) {
        sum--;
      }
      if (seat.contains("D") || seat.contains("F")) {
        sum--;
      }
    }
    return sum;
  }
}
